package com.dyz.LeetCodeforSwordFingerOffer;



import java.util.*;

public class LevelOrder_3 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(3);
        TreeNode node3 = new TreeNode(4);
        TreeNode node4 = new TreeNode(5);
        TreeNode node5 = new TreeNode(6);
        TreeNode node6 = new TreeNode(7);
        node2.left = node5;
        node2.right = node6;
        node1.left = node3;
        node1.right = node4;
        root.left = node1;
        root.right = node2;
        List<List<Integer>> print = new LevelOrder_3().levelOrder(root);
        System.out.println(print);
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res= new ArrayList<>();
        if (root==null){return res;}
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int direction = 1;
        while (!queue.isEmpty()){
            List<Integer> list = new ArrayList<>();
            Queue<TreeNode> pre = new LinkedList<>();
            int size = queue.size();
            for(int i=0; i<size;i++){
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left!=null){pre.add(node.left);}
                if(node.right!=null){pre.add(node.right);}
            }
            if(direction%2!=0){
                Collections.reverse(list);
            }
            res.add(list);
            direction++;
            queue=pre;

        }
        return res;
    }
}
